package net.deiangi.graphs.path;

import net.deiangi.graphs.core.Edge;
import net.deiangi.graphs.core.Graph;
import net.deiangi.graphs.core.Node;
import net.deiangi.graphs.ui.ProgressReporter;

import java.util.Arrays;
import java.util.LinkedList;

/**
 * User: Deian
 * Date: Nov 1, 2009
 * Time: 3:05:20 PM
 * <p/>
 * 1  function Dijkstra(Graph, source):
 * 2      for each vertex v in Graph:           // Initializations
 * 3          dist[v] := infinity               // Unknown distance function from source to v
 * 4          previous[v] := undefined          // Previous node in optimal path from source
 * 5      dist[source] := 0                     // Distance from source to source
 * 6      Q := the set of all nodes in Graph
 * // All nodes in the graph are unoptimized - thus are in Q
 * 7      while Q is not empty:                 // The main loop
 * 8          u := vertex in Q with smallest dist[]
 * 9          if dist[u] = infinity:
 * 10              break                         // all remaining vertices are inaccessible from source
 * 11          remove u from Q
 * 12          for each neighbor v of u:         // where v has not yet been removed from Q.
 * 13              alt := dist[u] + dist_between(u, v)
 * 14              if alt < dist[v]:             // Relax (u,v,a)
 * 15                  dist[v] := alt
 * 16                  previous[v] := u
 * 17      return dist[]
 * <p/>
 * If we are only interested in a shortest path between vertices source and target, we can terminate the search at line 12 if u = target. Now we can read the shortest path from source to target by iteration:
 * <p/>
 * 1  S := empty sequence
 * 2  u := target
 * 3  while previous[u] is defined:
 * 4      insert u at the beginning of S
 * 5      u := previous[u]
 */
public class Dijkstra {
    private Graph g;

    public Dijkstra(Graph graph) {
        this.g = graph;
    }

    public String shortest(String src, String target, ProgressReporter report) {
        int sI = g.indexOfNode(src, false);
        int tI = g.indexOfNode(target, false);

        int[] dist = new int[g.nodes.size()];
        int[] previous = new int[g.nodes.size()];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[sI] = 0;
        //        Map<Integer, Node> q = new HashMap<Integer,Node>();
        //        for(Node n : g.nodes) { q.put(n.i, n); }
        LinkedList<Node> q = new LinkedList<Node>(g.nodes);
        while (q.size() > 0) {
            // node in Q with smallest dist[]
            Node u = null;
            int minV = Integer.MAX_VALUE;
            for (Node n : q) {
                if (dist[n.i] < minV) {
                    minV = dist[n.i];
                    u = n;
                }
            }

            //
            if (dist[u.i] == Integer.MAX_VALUE) {
                // target not accessible from src
                break;
            }
            q.remove(u);
            if (u.i == tI) {

                for (int c = tI; c != sI; c = previous[c]) {
                    report.noteToNode(g.nodes.get(c), String.format(" * %d", dist[g.nodes.get(c).i]));
                }
                return String.format("done");
            }
            for (Edge v : u.to) {
                int altDist = dist[u.i] + v.w;
                if (altDist < dist[v.ti]) {
                    //report.noteToEdge(v, " best edge");
                    dist[v.ti] = altDist;
                    previous[v.ti] = u.i;
                }
            }

            String msg = String.format("dist[] = %s\nprev[] = %s ", arrayToString(dist), arrayToString(previous));
            report.report(msg);
        }

        return "";
    }

    private String arrayToString(int[] intArray) {
        StringBuffer sb = new StringBuffer();
        sb.append("{");
        for (int i : intArray) {
            sb.append(i).append(",");
        }
        sb.setCharAt(sb.length() - 1, '}');
        return sb.toString();
    }
}
